package Day4;

public class day04_02 {
}

class Solution {
    int n,m;
    int[] dx = { 0, 0,1,-1};
    int[] dy = { -1, 1,0,0};
    boolean vis[][];
    char[] word1;
    public boolean exist (String[] board, String word) {
        m = board.length;
        n = board[0].length();
        vis = new boolean[m][n];
        word1 = word.toCharArray();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(word1[0] == board[i].charAt(j)) {
                    if(dfs(board,i,j,0)) return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(String[] board,int i, int j, int pos) {
        if(pos == word1.length - 1) return true;
        vis[i][j] = true;
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >=0 && x < m
                    && y >=0 && y < n
                    && !vis[x][y]
                    && board[x].charAt(y) == word1[pos + 1]) {
                if(dfs(board,x,y,pos+1)) return true;
            }
        }
        vis[i][j] = false;
        return false;
    }
}
//https://www.nowcoder.com/practice/987f2981769048abaf6180ed63266bb2?tpId=196&tqId=39583&ru=/exam/oj